package thired.class11_digui;

public class Class24_NQueens {
        public static int num1(int n) {
            if(n < 1){
                return 0;
            }
            int[] record = new int[n];
            return process(0,record,n);
        }

        public static int process(int i, int[] record, int n){
            if(i == n){
                return 1;
            }
            int res = 0;
            for(int j = 0;j < n;j++){
                if(isValid(record,i,j)){
                    record[i] = j;
                    res += process(i + 1,record,n);
                }
            }
            return res;
    }

    public static boolean isValid(int[] record, int i, int j) {
        // 0..i-1
        for (int k = 0; k < i; k++) {
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }


    public static int num2(int n){
            if(n < 1 || n > 32){
                return 0;
            }
            int limit = n == 32 ? -1 : (1 << n) - 1;
            return process1(limit,0,0,0);
    }
    public static int process1(int limit,int colLim,int leftDiaLim,int rightDiaLim){
            if(colLim == limit){
                return 1;
            }
            int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
            int mostRightOne = 0;
            int res = 0;
            while (pos != 0){
                mostRightOne = pos & (-pos);
                pos = pos - mostRightOne;
                res += process1(limit,colLim | mostRightOne,(leftDiaLim | mostRightOne) << 1,
                        (rightDiaLim | mostRightOne) >>> 1);
            }
            return res;

    }
    public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == limit) {
            return 1;
        }
        // pos中所有是1的位置，是你可以去尝试皇后的位置
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0) {
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1,
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }

    public static void main(String[] args) {
        int n = 15;

        long start = System.currentTimeMillis();
        System.out.println(num2(n));
        long end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        System.out.println(num1(n));
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

    }
}
